# -*- coding: utf-8 -*-            
# @Time : 2022/11/24 22:40
# @Author  : lining
# @FileName: 插入排序.py
"""
插入排序：左边是顺序区，从右边的元素中取出最小的数插入左边顺序区的末尾
稳定性排序应用
订单，根据金额和时间排序，相同金额根据时间排序，先根据时间排序，然后把金额进行排序
1.先根据金额进行排序，然后根据时间排序
遍历数据，每次要找到金额相同的数据的开始和结束，然后对这部分数据进行时间排序
2.先根据时间进行排序，然后把金额排序
按照时间排序后时间已经是有序的，然后把金额排序，用稳定性的排序方法， 不需要考虑时间的问题，直接把整体按照金额排序即可
插入排序：最好O(n),已经有序不需要搬运数据，最坏O(n*n)，是原地排序，稳定排序
a = [6,5,4,3,2,1,0]
"""
class InsertSort():
    def insertsort(self, data_list):
        for i in range(1, len(data_list)):
            current = data_list[i]
            for y in range(i - 1, -1, -1):
                if current > data_list[y]:
                    data_list[y + 1] = current
                    break
                data_list[y + 1] = data_list[y]
                if y == 0:
                    data_list[0] = current
        # len_data = len(data_list)
        # for i in range(1, len_data):
        #     a = data_list[i]
        #     for x in range(i-1, -1, -1):
        #         if a < data_list[x]:
        #             data_list[x+1] = data_list[x]
        #         if x == 0 or a > data_list[x]:
        #             data_list[x] = a
        #             break
        print(data_list)


# a = [6,5,4,3,2,1,0]
a = [1,3,5,7,9,2,4,6,8,0,11]
InsertSort().insertsort(a)

